#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;

signed main() {
    int T;
    freopen("in.txt", "r", stdin);
    freopen("std.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        vector<int> l(n + 1, 0), r(n + 1, 0);
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                l[i] = ++cnt;
            } else
                cnt = 0;
        }
        cnt = 0;
        for (int i = n - 1; ~i; --i) {
            if (s[i] == '0')
                r[i] = ++cnt;
            else
                cnt = 0;
        }
        int mx(0);
        vector<int> v(1);
        for (int i = 0, cnt(0); i < n; ++i) {
            if (s[i] == '0')
                ++cnt;
            else {
                if (cnt) {
                    v.emplace_back(cnt);
                    cnt = 0;
                }
                v.emplace_back(0);
                continue;
            }
            if (i == n - 1) v.emplace_back(cnt);
        }
        v[1] *= 2, v.back() *= 2;
        v.emplace_back(0);
        vector<bool> vis(v.size() + 10);
        for (auto i : v) mx = max(mx, i);
        if (mx <= 1) {
            cout << mx << '\n';
            continue;
        }
        for (int i = 1; i < v.size() - 1; ++i) {
            if (v[i] == mx) {
                vis[i - 1] = 1;
                v[i] -= 1;
            }
        }
        // for(int i=0;i<v.size();++i) {
        //     cout<<v[i]<<' '<<vis[i]<<'\n';
        // }
        int ans(0);
        for (int i = 1; i < v.size() - 1; ++i) {
            if (v[i] == mx - 1) {
                if (vis[i - 1] && vis[i + 1]) {
                    ans = 1 + (v[i] + 1) / 2;
                    break;
                }
                if (vis[i + 1])
                    vis[i - 1] = 1;
                else
                    vis[i + 1] = 1;
                v[i] -= 1;
            }
        }
        if (!ans) ans = 1 + (mx - 2 + 1) / 2;
        cout << ans << '\n';
        // rep(i, 1, n - 1) {
        //     if (s[i] == '1' and s[i - 1] == '0' and s[i + 1] == '0') {
        //         int pos = i, cl = 0, cr = 0;
        //     }
        // }
    }
    return 0;
}